package LeetCode._01_树;

import java.util.TreeMap;

/**
 * https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/
 */
public class _114_二叉树展开为链表 {
    public class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val,TreeNode left,TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    //函数定义:输入一个根节点，将该节点拉成一条链表
    public void flatten(TreeNode root) {
        if(root == null) return;

        //将根节点的左子树和右子树都拉成一条链表
        flatten(root.left);
        flatten(root.right);

        TreeNode left = root.left;
        TreeNode right = root.right;

        root.left = null; //断开左子树
        root.right = left; //左子树接上右边
        TreeNode p = root;
        while(p.right!=null){
            p = p.right; //遍历原来的左子树，直到最后
        }
        p.right = right; //接上原来的右子树
    }

}
